home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / 2DLab / touropt.m < prev    next >
Encoding:
Text File  |  1992-01-14  |  8.7 KB  |  262 lines
  1.  
  2. #include <stdlib.h>
  3. #ifdef MYDIR
  4. #else
  5. #include "TwoDView.h"
  6. #include "TwoDTSP.h"
  7. #include <appkit/graphics.h>
  8. #endif
  9. #include <math.h>
  10. #include <limits.h>
  11. #include <stdio.h>
  12. #include "tspheaders.h"
  13. #include "prototypes.h"
  14. extern   setUpScaling(TwoDView *);
  15. extern   setUpDrawing(TwoDView *);
  16. /************************************************************************/
  17. /* This function implements a (2-Opt) Tour Optimization Algorithm for the
  18.    Travelling Salesperson Algorithm.  It provides an approximate optimal
  19.    value rather than the optimal value. 
  20.  
  21.    Reference: Salkin & Mathur, Foundations Of Integer Programming, 1989
  22.               North-Holland, p 690-93.
  23. */
  24. /************************************************************************/
  25. /* Parameters:   TwoDView *self: Ye Old Drawing Object
  26.  
  27.                     float *Data: Pointer to the list of points.
  28.                                  Used to draw intermediate graph.
  29.  
  30.                 float *Distance: Pointer to area that contains the
  31.                                  Distances Between Each Pair of Cities
  32.  
  33.                       int *Tour: Pointer to area that will contain the
  34.                                  indices of the n arcs that are selected 
  35.                                  to be a part of the tour
  36.  
  37.              int NumberOfCities: Number of cities in the problem
  38. */
  39. /************************************************************************/
  40. /************************************************************************/
  41. #ifdef MYDIR
  42. float TourOptimization(float *Distance,int *Tour,float OptimalValue, 
  43.                        int NumberOfCities) {
  44. #else
  45. float TourOptimization(TwoDView *self,float *data,float *Distance,int *Tour,
  46.                        float OptimalValue, int NumberOfCities) {
  47. #endif
  48.  
  49. int i,CurrentEdge,CurrentFrom,CurrentTo,NumberOfExchanges,
  50.     NextEdge,NextFrom,NextTo,Exchanges,ExchangeEdge1,ExchangeEdge2,
  51.     NewFrom1,NewFrom2,NewTo1,NewTo2;
  52. float OnTourDistance1,OnTourDistance2,NotOnTourDistance1,NotOnTourDistance2,
  53.       BestExchange,Gain,NewOptimalValue;
  54. char msg[256];
  55.  
  56. #ifndef MYDIR /* code to set up drawing enviromment */
  57.         self->displayFlag = DISP_PTS_ONLY;
  58.         [self display];
  59.  
  60.     [self lockFocus];
  61.       setUpScaling(self);
  62.       NXSetColor([self->highColorWell color]);
  63.       setUpDrawing(self);
  64.       PSsetinstance(YES);
  65.         PSnewinstance();
  66.         for (i=0;i<2*(NumberOfCities);i+=2) {
  67.          int x,y;
  68.          x = Tour[i];
  69.          y = Tour[i+1];
  70.          [self drawEdge:X(x):Y(x):X(y):Y(y)];
  71.     }
  72.         NXPing();    
  73. #endif
  74.  
  75.  NewOptimalValue = OptimalValue;
  76.     
  77.  Exchanges = 1;
  78.  NumberOfExchanges = 0;
  79.  
  80.  /* while at least 1 edge exchange has ocurred, we must look and see if
  81.     this change might make others possible. */
  82.  while (Exchanges) {
  83.    Exchanges = 0;
  84.    BestExchange = 0;
  85.    CurrentEdge = 0;
  86.  
  87.    /* for all edges on the tour, and look at all possible edge
  88.       exchanges. */
  89.    while (CurrentEdge < NumberOfCities) {
  90.  
  91.  #ifdef DEBUGMYDIR
  92.      printf("comparing edge %d with all other edges \n",CurrentEdge);
  93.  #else
  94.      sprintf(msg,"comparing edge %d with all other edges \n",CurrentEdge);
  95.      STATUS(msg);
  96.  #endif
  97.  
  98.      CurrentFrom = Tour[2*CurrentEdge];
  99.      CurrentTo = Tour[2*CurrentEdge+1];
  100.      OnTourDistance1 = Distance[kfrom(CurrentFrom,CurrentTo,NumberOfCities)];
  101.      NextEdge = CurrentEdge + 1;
  102.  
  103.      /* look at all edges on the tour that we might be able to make an
  104.         exchange with CurrentEdge. */
  105.      while (NextEdge < NumberOfCities) {
  106.        NextFrom = Tour[2*NextEdge];
  107.        NextTo = Tour[2*NextEdge+1];
  108.  
  109.        /* we can't look at edges that involve CurrentFrom or CurrentTo.*/
  110.        if ((NextFrom != CurrentFrom) & 
  111.           (NextFrom != CurrentTo)) {
  112.          if ((NextTo != CurrentFrom) &
  113.              (NextTo != CurrentTo)) {
  114.  
  115.            /* Get distance between NextFrom and NextTo. */
  116.            OnTourDistance2 = Distance[kfrom(NextFrom,NextTo,NumberOfCities)];
  117.  
  118.            /* first look at exchanging CurrentFrom to CurrentTo and
  119.               NextFrom to NextTo with CurrentFrom to NextFrom and
  120.               CurrentTo to NextTo. */
  121.            NotOnTourDistance1 = 
  122.              Distance[kfrom(CurrentFrom,NextFrom,NumberOfCities)];
  123.            NotOnTourDistance2 = 
  124.              Distance[kfrom(CurrentTo,NextTo,NumberOfCities)];
  125.  
  126.            Gain = (NotOnTourDistance1 + NotOnTourDistance2) -
  127.                   (OnTourDistance1 + OnTourDistance2);
  128.  
  129.            /* If there is a negative gain, this is a candidate for the 
  130.               best exchange in this iteration. */
  131.            if (Gain < BestExchange) {
  132.             if (ValidTour(Tour,CurrentEdge,NextEdge,0,NumberOfCities)) {
  133.  #ifdef DEBUGMYDIR
  134.                printf("Changing BestExchange from %f to %f \n",BestExchange,Gain);
  135.  #endif
  136.                BestExchange = Gain;
  137.                ExchangeEdge1 = CurrentEdge;
  138.                ExchangeEdge2 = NextEdge;
  139.  #ifdef DEBUGMYDIR
  140.                printf("Changing NewFrom1 from %d to %d \n",NewFrom1,CurrentFrom);
  141.                printf("Changing NewTo1 from %d to %d \n",NewTo1,NextFrom);
  142.                printf("Changing NewFrom2 from %d to %d \n",NewFrom2,CurrentTo);
  143.                printf("Changing NewTo2 from %d to %d \n",NewTo2,NextTo);
  144.  #endif
  145.                NewFrom1 = CurrentFrom;
  146.                NewTo1 = NextFrom;
  147.                NewFrom2 = CurrentTo;
  148.                NewTo2 = NextTo;
  149.              }
  150.            }  
  151.  
  152.            /* next look at exchanging CurrentFrom to CurrentTo and
  153.               NextFrom to NextTo with CurrentFrom to NextTo and
  154.               CurrentTo to NextFrom. */
  155.            NotOnTourDistance1 = 
  156.              Distance[kfrom(CurrentFrom,NextTo,NumberOfCities)];
  157.            NotOnTourDistance2 = 
  158.              Distance[kfrom(CurrentTo,NextFrom,NumberOfCities)];
  159.  
  160.            Gain = (NotOnTourDistance1 + NotOnTourDistance2) -
  161.                   (OnTourDistance1 + OnTourDistance2);
  162.  
  163.            /* If there is a negative gain, this is a candidate for the 
  164.               best exchange in this iteration. */
  165.            if (Gain < BestExchange) {
  166.             if (ValidTour(Tour,CurrentEdge,NextEdge,1,NumberOfCities)) {
  167.  #ifdef DEBUGMYDIR
  168.                printf("Changing BestExchange from %f to %f \n",BestExchange,Gain);
  169.  #endif
  170.                BestExchange = Gain;
  171.                ExchangeEdge1 = CurrentEdge;
  172.                ExchangeEdge2 = NextEdge;
  173.  #ifdef DEBUGMYDIR
  174.                printf("Changing NewFrom1 from %d to %d \n",NewFrom1,CurrentFrom);
  175.                printf("Changing NewTo1 from %d to %d \n",NewTo1,NextTo);
  176.                printf("Changing NewFrom2 from %d to %d \n",NewFrom2,CurrentTo);
  177.                printf("Changing NewTo2 from %d to %d \n",NewTo2,NextFrom);
  178.  #endif
  179.                NewFrom1 = CurrentFrom;
  180.                NewTo1 = NextTo;
  181.                NewFrom2 = CurrentTo;
  182.                NewTo2 = NextFrom;
  183.              }
  184.            }  
  185.          }
  186.        }
  187.  
  188.        /* get ready to look at the next edge on the tour. */
  189.        NextEdge+=1;
  190.  
  191.        /* perhaps we have looked at all exchanges for this edge...*/
  192.        if (NextEdge == NumberOfCities) {
  193.  #ifdef DEBUGMYDIR
  194.          printf("done looking at edge %d \n",CurrentEdge);
  195.  #else
  196.          sprintf(msg,"done looking at edge %d \n",CurrentEdge);
  197.          STATUS(msg);
  198.  #endif
  199.        }
  200.      }
  201.   
  202.      /* Now look at the next city on the tour. */
  203.      CurrentEdge+=1;
  204.    }
  205.    
  206.    /* we've looked at all possible exchanges.  now, if BestExchange is 
  207.       greater than 0, we have a valid exchange that will lead to a 
  208.       better tour. */
  209.    if (BestExchange < 0) {
  210.  #ifdef DEBUGMYDIR
  211.      printf("Found an exchange \n");
  212.      printf("ExchangeEdge1 %d ExchangeEdge2 %d \n",ExchangeEdge1,ExchangeEdge2);
  213.  #else
  214.      sprintf(msg,"exchanging edges %d and %d \n",
  215.                   ExchangeEdge1,ExchangeEdge2);
  216.      STATUS(msg);
  217.  #endif
  218.      Tour[2*ExchangeEdge1] = NewFrom1;
  219.      Tour[2*ExchangeEdge1+1] = NewTo1;
  220.      Tour[2*ExchangeEdge2] = NewFrom2;
  221.      Tour[2*ExchangeEdge2+1] = NewTo2;
  222.      NewOptimalValue+= BestExchange;
  223.      Exchanges = 1;
  224.      NumberOfExchanges+=1;
  225.      BestExchange = 0;
  226.  #ifndef MYDIR
  227.      /* draw the intermediate tour */
  228.      PSnewinstance();
  229.      for (i=0;i<2*(NumberOfCities);i+=2) {
  230.        int x,y;
  231.        x = Tour[i];
  232.        y = Tour[i+1];
  233.        [self drawEdge:X(x):Y(x):X(y):Y(y)];
  234.      }
  235.      sprintf(msg,"number of exchanges: %d \n",NumberOfExchanges);
  236.      STATUS(msg);
  237.      NXPing();
  238.      [self->optimalValueField setFloatValue: NewOptimalValue at: 0];
  239.      usleep(self->drawTime);
  240. #endif
  241.    }
  242.            
  243.  #ifdef DEBUGMYDIR
  244.      /* print out current subtour */
  245.      printf("number of exchanges: %d \n",NumberOfExchanges);
  246.      for (i=0;i<2*(NumberOfCities);i+=2) {
  247.        printf("i %d from city %d to city %d \n",i,Tour[i],Tour[i+1]);
  248.      }
  249.  #endif
  250.     
  251. }
  252. #ifndef MYDIR
  253.     PSsetinstance(NO);
  254.     [self unlockFocus];
  255.         self->displayFlag = DISP_PTS_RESULTS;
  256.         [self display];
  257. #endif
  258.  
  259. /* return the optimal value */
  260. return(NewOptimalValue);
  261. }
  262.